COMPX546-23B (HAM)

Graph Theory

15 Points

Edit Header Content
The University of Waikato
Academic Divisions
Division of Health Engineering Computing & Science
School of Computing and Mathematical Sciences Office
Department of Mathematics

Staff

Edit Staff Content

Convenor(s)

Nicholas Cavenagh

Nicholas Cavenagh
8329
G.3.25
See Moodle
nicholas.cavenagh@waikato.ac.nz

Lecturer(s)

Administrator(s)

: maria.admiraal@waikato.ac.nz

Placement/WIL Coordinator(s)

Tutor(s)

Student Representative(s)

Lab Technician(s)

Librarian(s)

: anne.ferrier-watson@waikato.ac.nz

You can contact staff by:

  • Calling +64 7 838 4466 select option 1, then enter the extension.
  • Extensions starting with 4, 5, 9 or 3 can also be direct dialled:
    • For extensions starting with 4: dial +64 7 838 extension.
    • For extensions starting with 5: dial +64 7 858 extension.
    • For extensions starting with 9: dial +64 7 837 extension.
    • For extensions starting with 3: dial +64 7 2620 + the last 3 digits of the extension e.g. 3123 = +64 7 262 0123.
Edit Staff Content

What this paper is about

Edit What this paper is about Content
Graph theory and combinatorics, including: admissible degree sequences, connectivity, Eulerian graphs, Hamiltonian graphs, planarity, graph colourings, network flows, matchings and related topics in combinatorics. Particular attention will be focused on graph theory algorithms such as the travelling salesman problem and max flow/min cut, including applications
Edit What this paper is about Content

How this paper will be taught

Edit How this paper will be taught Content
The paper will be delivered via three contact hours per week, which will be a mixture of lecture and tutorial-style learning. It is recommended students attend lectures in person, because of interactive activities and the need of extensive whiteboard space to teach advanced mathematics.
Edit How this paper will be taught Content

Required Readings

Edit Required Readings Content
Any required readings will be available on MOODLE at no cost.
Edit Required Readings Content

Learning Outcomes

Edit Learning Outcomes Content

Students who successfully complete the course should be able to:

  • Understand concepts and solve graduate-level problems in the topics: Flows in networks, matchings and 1-factors, Latin squares, graph decompositions, balanced incomplete block designs, design theory and related topics
    Linked to the following assessments:
    • Assignment 1 (1)
    • Assignment 2 (2)
    • Assignment 3 (3)
    • Assignment 4 (4)
    • Assignment 5 (5)
    • Project (6)
  • Gain awareness of the importance of real-world applications of these topics, in particular algorithms such as the traveling salesman problem, maxflow/mincut and matchings
    Linked to the following assessments:
    • Assignment 1 (1)
    • Assignment 2 (2)
    • Assignment 3 (3)
    • Assignment 4 (4)
    • Assignment 5 (5)
    • Project (6)
  • Develop advanced skills in reading, writing and understanding pure mathematical proofs
    Linked to the following assessments:
    • Assignment 1 (1)
    • Assignment 2 (2)
    • Assignment 3 (3)
    • Assignment 4 (4)
    • Assignment 5 (5)
    • Project (6)
  • Develop advanced skills in mathematical problem solving, combining creativity in ideas with exposition and clarity in presentation of solutions
    Linked to the following assessments:
    • Assignment 1 (1)
    • Assignment 2 (2)
    • Assignment 3 (3)
    • Assignment 4 (4)
    • Assignment 5 (5)
    • Project (6)
Edit Learning Outcomes Content
Edit Learning Outcomes Content

Assessments

Edit Assessments Content

How you will be assessed

Edit How you will be assessed Content

The assessment consists of five assignments, each worth 15% and one project, worth 25%. The project consists of a report worth 20% and a 10 minute oral presentation during class in the week October 9th-13th worth 5%.

In the assignment work students can pick and choose between more theoretical proof-style questions and coding of algorithms, depending on their background and interests.

A preliminary deadline for the report is Wednesday, September 30th. Students who submit their report by this time will get feedback for improvement from the lecturer. The final deadline for the report is Friday October 20th.

The report will be marked on the ability of the student to use coherent and clear notation and communication as well as understanding of the topic. The target audience are your classmates rather than the lecturer. The report must include a proper bibliography with at least 3 different sources.

There are two options for the project:

Option 1: Theory Option

For the project, students must research a topic within combinatorics. Suggested topics are:

Steiner Triple Systems, Hadamard Matrices, Cycle Decompositions, Balanced Tournament Designs, Magic squares, Pairwise Balanced Designs, Linear Spaces, Lotto Designs, Ramsey Numbers, Partially Ordered Sets, Matroids.

Students may come up with their own topic at the lecturer's approval.

It should include definitions, examples and some elementary lemmas or theorems in the area. The report must include at least one non-trivial proof written in the student's own words.

Option 2: Applications Option

The student must research a real-world application of a combinatorial algorithm. Suggested algorithms/applications:

Depth first search/breadth first search; the A* search algorithm; the travelling salesman problem; bipartite matchings; vertex-colorings and timetabling; operations research; printed circuit board design; traffic networking.

Students may come up with their own topic at the lecturer's approval.

The project should include non-trivial examples explored via a package such as MATLAB; including a discussion of assumptions and limitations of the algorithm in question.

Edit How you will be assessed Content

The internal assessment/exam ratio (as stated in the University Calendar) is 100:0. There is no final exam. The final exam makes up 0% of the overall mark.

The internal assessment/exam ratio (as stated in the University Calendar) is 100:0 or 0:0, whichever is more favourable for the student. The final exam makes up either 0% or 0% of the overall mark.

Component DescriptionDue Date TimePercentage of overall markSubmission MethodCompulsory
1. Assignment 1
15
2. Assignment 2
15
3. Assignment 3
15
4. Assignment 4
15
5. Assignment 5
15
6. Project
20 Oct 2023
6:00 PM
25
Assessment Total:     100    
Failing to complete a compulsory assessment component of a paper will result in an IC grade
Edit Assessments Content